/*
 * @Author: 缄默
 * @Date: 2021-09-23 21:15:39
 * @LastEditors: 缄默
 * @LastEditTime: 2021-09-28 15:43:47
 */
 //求最大子矩阵大小

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
int findMaxMatrix(vector<vector<int>>& arr);
int findMaxArray(vector<int>& arr);

vector<vector<int>> rightWay(vector<int>& arr);

int main() {
    vector<vector<int>> arr({ {1, 0, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 0} });
    int max = findMaxMatrix(arr);
    cout << max << endl;
    return 0;

}

int findMaxMatrix(vector<vector<int>>& arr) {
    vector<int> height(arr[0].size(), 0);
    int max = 0;
    int temp = 0;
    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr[0].size(); j++) {
            height[j] = arr[i][j] == 1 ? height[j] + 1 : 0;
        }
        temp = findMaxArray(height);
        max = max < temp ? temp : max;
    }
    return max;
}

int findMaxArray(vector<int>& arr) {
    int max = 0;
    int temp = 0;
    vector<vector<int>> res = rightWay(arr);

    for (int i = 0; i < arr.size(); i++) {

        temp = (res[i][1] - res[i][0] - 1) * arr[i];
        max = max < temp ? temp : max;
    }
    return max;
}


//单调栈 找到小于它的左右最近的两个数
vector<vector<int>> rightWay(vector<int>& arr) {
    stack<int> stack;
    vector<vector<int>> res(arr.size(), vector<int>(2));
    int num;
    for (int i = 0; i < arr.size(); i++)
    {

        //注意单调栈的大小顺序 是栈底最大还是栈底最小
        //此处等于与大于等于均可
        //理由：我们找到这个值之后要做的是求出最大的面积，如果是大于弹出的话 则是第一个同样的值取得正确的右边界
        //如果是大于等于弹出的话 则是最后一个取得正确的左边界  总会有一个取得正确的边界  题目为求最大值 所以并不需要每一个值都是正确的
        while (!stack.empty() && arr[stack.top()] >= arr[i])
        {
            num = stack.top();
            stack.pop();
            res[num][1] = i;
            res[num][0] = stack.empty() ? -1 : stack.top();
        }
        if (!stack.empty()) {
            res[i][0] = stack.top();
        }
        else
        {
            res[i][0] = -1;
        }

        stack.push(i);
    }
    while (!stack.empty())
    {
        num = stack.top();
        res[num][1] = arr.size();
        stack.pop();
    }
    return res;
}